package dataStructure.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {
    public static void main(String[] args) {
//        String s="1+((2+3)*4)-5+10-26";
        String s="4*5-8+60+8/2";
        System.out.println(toInfixExpressionList(s));
//        toInfixExpressionList(s).forEach(System.out::println);
//        System.out.println(parseSuffixExpreesionList(toInfixExpressionList(s)));
//        System.out.println(parseSuffixExpreesionList(toInfixExpressionList(s)));
//        int result = calculate(parseSuffixExpreesionList(toInfixExpressionList(s)));
//        System.out.println(result);
    }
    //后缀表达式（逆波兰表达式）计算
    public static int calculate(List<String> ls){
        Stack<String> stack = new Stack<>();
        for (String item :ls){
            if (item.matches("\\d+")){
                stack.push(item);
            }else {
               int num1 =  Integer.parseInt(stack.pop());
               int num2 =  Integer.parseInt(stack.pop());
               int res = cal(num1,num2,item);
               stack.push(String.valueOf(res));
            }
        }
        return Integer.parseInt(stack.pop());
    }
    public static int cal(int num1,int num2,String oper){
        int res = 0;
        switch (oper){
            case "+" : res = num2+num1;break;
            case "-" : res = num2-num1;break;
            case "*" : res = num2*num1;break;
            case "/" : res = num2/num1;break;
            default: break;
        }
        return res;

    }

    //方法：将得到的中缀表达式对应的 List => 后缀表达式对应的 List
    public static List<String> parseSuffixExpreesionList(List<String> ls){
        Stack<String> s1 = new Stack<>();
        ArrayList<String> s2 = new ArrayList<>();
        for (String item :ls){
            if (item.matches("\\d+")){
                s2.add(item);
            }else if ("(".equals(item) ||s1.isEmpty()){
                s1.push(item);
            }else {
               if (")".equals(item)){
                   while (!("(".equals(s1.peek()))){
                       s2.add(s1.pop());
                   }
                   s1.pop();//左括号也出去
               }else {
                   while (s1.size() != 0&& Operation.getValue(item)<=Operation.getValue(s1.peek())){
                       s2.add(s1.pop());
                   }
                   s1.push(item);
               }
            }
        }
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;
    }



    //将一个逆波兰表达式， 依次将数据和运算符 放入到 ArrayList 中
    public static List<String> toInfixExpressionList(String s){
        String str;
        ArrayList<String> list = new ArrayList<>();
        int index=0;
        char c;
        do {
            //如果是非数字
            if ((c=s.charAt(index))<48||(c=s.charAt(index))>57){
                list.add(c+"");
                index++;
            }else {
                str = ""; //先将 str 置成"" '0'[48]->'9'[57]
                while (index<s.length() && (c=s.charAt(index)) >= 48 && (c=s.charAt(index)) <= 57){
                    str += c;
                    index++;
                }
                list.add(str);
            }

        }while (index<s.length());

        return list;
    }
}
class Operation{
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;
    public static int getValue(String operation) {
        int res =0;
        switch (operation){
            case "+": res = ADD;break;
            case "-": res = SUB;break;
            case "*": res = MUL;break;
            case "/": res = DIV;break;
            default:break;
        }
        return res;
    }
}


